package jianzhi_offer;

public class _3_重建二叉树 {
	public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return help(pre,in,0,pre.length-1,0,pre.length-1);
	}
	//用递归划分区间
	private TreeNode help(int[] pre,int[] in,int pre1,int pre2,int in1,int in2) {
		if(pre1 > pre2) return null;
		TreeNode root = new TreeNode(pre[pre1]);
		for(int i=in1;i<=in2;++i) {
			if(in[i] == pre[pre1]) {
				root.left = help(pre,in,pre1+1,pre1+i-in1,in1,i-1);
				root.right = help(pre,in,pre1+1+i-in1,pre2,i+1,in2);
			}
		}
		return root;
	}
	
	
	private int inIndex=0, preIndex=0;
	//用双指针
    public TreeNode reConstructBinaryTree_(int [] pre,int [] in) {
         return helper(pre, in, Integer.MAX_VALUE);
    }
    private TreeNode helper(int[] preorder, int[] inorder, int target) {
        if (inIndex >= inorder.length || inorder[inIndex] == target) {//该处只有一个节点 inorder[inIndex] == target 
        	//这是不构造节点的唯一条件 并且此时index都不会改变
        	return null;
        }  
        TreeNode root = new TreeNode(preorder[preIndex]);//先把先序的处理完  把先序的树构造好
        preIndex++;
        root.left = helper(preorder, inorder, root.val);//因为最靠近父节点的就是左子树的根 或者没有左子树
        inIndex++;
        root.right = helper(preorder, inorder, target);
        return root;
    }
}
